package org.example.myleet.p1109;

import java.util.Arrays;

public class Solution {

    /**
     * 官方解题思路：差分数组 + 前缀和，还原对应的位置的总和，O(n)
     * 回顾差分数组和前缀和这对互相转化概念：
     * 情况一、对于想要快速知道原数组中相邻元素的差值，可以对原数组求差分数组，要还原的时候可以通过求前缀和得到原数组
     * 例子：原数组a = [1,2,2,4]，想要知道[2,3]范围的差值，可以先求差分数组得到a = [1,1,0,2]，然后由a[3]得到[2,3]范围的差值
     * 情况二、对于想要快速知道原数组在某一段范围内的和值，可以对原数组求前缀和，要还原的时候可以通过求差分数组得到原数组
     * 例子：原数组[1,2,2,4]，想要知道[0,3]范围的和值，可以先求前缀和数组得到a = [1,3,5,9]，然后由a[3]得到[0,3]范围的和值
     * 想要知道[1,2]范围的和值由a[2] - a[0]得到
     * 本题中，差分数组的性质是，当我们希望对原数组的某一个区间 [l,r] 施加一个增量 inc 时，差分数组 d 对应的改变是：d[l]d[l] 增加 inc，d[r+1] 减少 inc。这样对于区间的修改就变为了对于两个位置的修改。并且这种修改是可以叠加的，即当我们多次对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。
     * 得到差分数组后，通过求前缀和就可以得到原数组，即结果
     */
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] totalArr = new int[n];
        for (int[] booking : bookings) {
            //求差分数组
            totalArr[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                //注意边界
                totalArr[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; ++i) {
            //求前缀和还原结果
            totalArr[i] += totalArr[i - 1];
        }
        return totalArr;
    }

    /**
     * 暴力模拟O(n^2)
     */
//    public int[] corpFlightBookings(int[][] bookings, int n) {
//        int[] totalArr = new int[n + 1];
//        for (int[] booking : bookings) {
//            for (int i = booking[0]; i <= booking[1]; ++i) {
//                totalArr[i] += booking[2];
//            }
//        }
//        return Arrays.copyOfRange(totalArr, 1, n + 1);
//    }
}
